package Hot100;

/**
 * @author zhangmin
 * @create 2022-01-04 11:13
 */
public class productExceptSelf238 {

    /**
     * 238. 除自身以外数组的乘积
     * 给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
     * 思路：计算前缀乘积，后缀乘积
     * */
    public int[] productExceptSelf(int[] nums) {
        int n=nums.length;
        int[] pre=new int[n],post=new int[n];
        pre[0]=nums[0];
        post[n-1]=nums[n-1];
        for (int i = 1; i < n; i++) {
            pre[i]=pre[i-1]*nums[i];
            post[n-i-1]=post[n-i]*nums[n-i-1];
        }
        int[] res=new int[n];
        res[0]=post[1];
        res[n-1]=pre[n-2];
        for (int i = 1; i < n-1; i++) {
            res[i]=pre[i-1]*post[i+1];
        }
        return res;
    }

}
